package pagerank;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;
import java.util.Stack;

import pagerank.BoardStruct;

public class FLQuickSort_NoRec  {
	public static int THRESHOLD = 8;
	public static Random pivotRandom = new Random();
	static 
	{
		pivotRandom.setSeed(System.currentTimeMillis());
	}
	protected static int compareOneToTwo(FLURLPageRankStruct x, FLURLPageRankStruct y)
	{
		if (x.PageRankValue < y.PageRankValue)
		{
			return -1;
		}
		else if(x.PageRankValue > y.PageRankValue)
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}
	public static int selectPivot(int left, int right)
	{
//		return (left + right) / 2;
		int pivot = Math.abs(pivotRandom.nextInt()) % (right - left) + left;
		return pivot;
	}
	public static int partition(ArrayList<FLURLPageRankStruct> des, int left, int right ,int pivot)
	{
		FLURLPageRankStruct temp = des.get(pivot);
		des.set(pivot, des.get(right));
//		des.set(right, temp);
		int i = left;
		int j = right;
		while( i != j)
		{
			while (compareOneToTwo(des.get(i),temp) < 0 && i < j)
				i++;
			if (i < j)
			{
				des.set(j, des.get(i));
				j --;
			}
			while (compareOneToTwo(des.get(j),temp) > 0 && i < j)
				j --;
			if (i < j)
			{
				des.set(i, des.get(j));
				i ++;
			}
		}
		des.set(i, temp);
		return i;
	}
	
	protected static void qsort(ArrayList<FLURLPageRankStruct> des, int indexLeft, int indexRight)
	{
		Stack<BoardStruct> boardStack = new Stack<BoardStruct>();
		BoardStruct oneBoard = new BoardStruct(indexLeft, indexRight);
		boardStack.add(oneBoard);
		
		while(! boardStack.isEmpty())
		{
			BoardStruct thisBoard = boardStack.pop();
			if (thisBoard.left >= thisBoard.right)
			{
				continue;
			}
			else if (thisBoard.right - thisBoard.left + 1 <= THRESHOLD)
			{
				for (int i=thisBoard.left + 1; i<= thisBoard.right; i++)
				{
					FLURLPageRankStruct temp = des.get(i);
					int j = i - 1;
					while (j >= thisBoard.left && compareOneToTwo(des.get(j),temp) > 0)
					{
						des.set(j + 1, des.get(j));
						j = j - 1;
					}
					des.set(j + 1, temp);
				}
				continue;
			}
			int pivot = selectPivot(thisBoard.left, thisBoard.right);
			pivot = partition(des, thisBoard.left, thisBoard.right, pivot);
			BoardStruct leftBoard = new BoardStruct(thisBoard.left, pivot - 1);
			boardStack.push(leftBoard);
			BoardStruct rightBoard = new BoardStruct( pivot + 1, thisBoard.right);
			boardStack.push(rightBoard);
		}
	}
	public static void main(String args[])
	{
		ArrayList<FLURLPageRankStruct> a = new ArrayList<FLURLPageRankStruct>();
//		a.add(new FLURLPageRankStruct("fl0.3",0.3));
//		a.add(new FLURLPageRankStruct("fl0.4",0.4));
//		a.add(new FLURLPageRankStruct("fl0.1",0.1));
//		a.add(new FLURLPageRankStruct("fl0.001",0.001));
//		a.add(new FLURLPageRankStruct("fl0.01",0.01));
//		a.add(new FLURLPageRankStruct("fl0.01",0.01));
		
		File dataFile = new File("123PageRankResult.txt");
//		File dataFile = new File("123.txt");
		FileReader fr;
		try {
			fr = new FileReader(dataFile);
			BufferedReader br = new BufferedReader(fr);
			String oneString;
			oneString = br.readLine();
			int count = 0;
			while (oneString != null)
			{
				String thisURL,thisPA;
				String[] as = oneString.split(",");
				thisURL = as[1];
				thisPA = as[2];
				FLURLPageRankStruct thisStruct = new FLURLPageRankStruct(thisURL, Double.parseDouble(thisPA));
				a.add(thisStruct);
				oneString = br.readLine();
				count++;
//				if (count > 5000)
//					break;
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		long start = System.currentTimeMillis();
		qsort(a,0,a.size()-1);
		long end = System.currentTimeMillis();
		System.out.println("use time: " + (end - start));
		for (int i=0; i<a.size(); i++)
		{
		//	System.out.println(a.get(i));
			if (i > 0)
			{
				if (a.get(i-1).PageRankValue > a.get(i).PageRankValue)
				{
					System.out.println("Wrong");
					break;
				}
			}
		}
	}
}
